The invention relates generally to two-dimensional barcodes, and, more particularly, to a robust clock free two-dimensional barcode symbology, encoding information formatted in such barcode symbology, printing the barcode symbology onto a printed medium, and decoding the same.
Contrary to the frequent predictions that we will one day live in a xe2x80x9cpaperless societyxe2x80x9d, paper, and other printed mediums, are playing an increasingly important role as an inexpensive, effective and convenient means for communication. A fundamental limitation with paper, however, is that from a computer standpoint, it is currently an output-only format. While paper may be the preferred medium for displaying information for human use, it is difficult, if not impossible, for a computer to recover data reliably once it has been printed. Optical character recognition (OCR) attempts to solve this problem in a relatively simple domain, such as text rendered using standard fonts, but has met with only limited success thus far. While accuracy rates of ninety-nine (99%) percent are perhaps achievable and may seem impressive, a page with 3,000 characters will still incur an average of thirty (30) OCR errors and hence requires expensive and time consuming manual post-processing.
Another approach uses computer readable barcodes which may be included directly on paper (or other printed medium such as microfilm). Once encoded, such barcodes can be used by the computer to recover information evident to the human reader but difficult for a computer to recognize (e.g., printed text), information implicit to the creation of page but essentially invisible to the human reader (e.g., spreadsheet formulas), or any other information desired, whether or not dependent on the actual character text on the paper.
Computer readable barcodes, wherein digital data is recorded directly on paper, are known and have been utilized to provide document or product identification given a fixed set of values using simple numeric encoding and scanning technologies. Document or product identification systems which have been employed in the past include barcode markers and scanners which have found use in a wide range of arenas. With respect to paper documents, special marks or patterns in the paper have been used to provide information to a related piece of equipment, for example the job control sheet for image processing as taught by Hikawa in U.S. Pat. No. 5,051,779. Similarly, identifying marks comprising encoded information have been printed on the face of preprinted forms as described in U.S. Pat. No. 5,060,980 to Johnson, et al. The Johnson, et al. system provides for a user entering hand drawn information in the fields on a paper copy of the form and then scanning the form to provide insertions to the fields in the duplicate form that is stored electronically in the computer. Still another system is described in U.S. Pat. No. 5,091,966 of Bloomberg, et al., which teach the decoding of glyph shape codes, which codes are digitally encoded data on paper. The identifying codes can be read by a computer and thereby facilitate computer handling of the document, such as identifying, retrieving and transmitting such document.
Besides the various shaped barcodes described above, two-dimensional barcodes called xe2x80x9cdata stripsxe2x80x9d having a plurality of rows of xe2x80x9cdata linesxe2x80x9d that represent information digitally encoded on printed media are also known in the art. Each data line row consists of a series of black and white pixels each representing binary xe2x80x9c0xe2x80x9ds and xe2x80x9c1xe2x80x9ds. The ordering of the bits in each row determines the digital data stored therein. The data stored within the totality of the rows define the data contained in the two-dimensional barcode. Typically, to read the barcode, the user passes a hand scanner, which simultaneously reads the information in each data line row, vertically along the length of the barcode to read all of the data line rows.
An example of a prior art system using a data strip two-dimensional barcode having rows of data lines with paper media, is found in U.S. Pat. Nos. 4,692,603, 4,754,127 and 4,782,221 of Brass, et al. In this system, two-dimensional barcodes consist of data line rows which are used to encode computer programs and data on paper and are scanned by use of a hand scanner. In addition to encoding the computer programs and data, these data lines also contain tracking and synchronization bits, hereinafter referred to as xe2x80x9cclock bitsxe2x80x9d. The requirement for use of numerous clock bits directly within each data line row, significantly reduces the amount of digital data that can be stored within each row. Further, if data line rows having clock bits are damaged, which is common if such barcodes are photocopied or transmitted by facsimile systems, such clock bits would be lost making it difficult, if not impossible, to decode the information encoded in the barcode.
U.S. Pat. No. 5,083,214 of Knowles describes a two-dimensional barcode system that also requires embedding clock bits within the encoded data itself. However, instead of encoding every row and column of data with synchronization and clock bits, the Knowles ""214 Patent uses the uppermost row in a data barcode to provide synchronization during scanning. Further, the first eight left most columns of bits comprise clock bits that are used for establishing the clocks to read the data bits contained in each row. Since the uppermost row and all eight left-most columns of the two-dimensional barcode, described in the Knowles ""214 Patent, are used solely for synchronization and clocking, the overall data capacity of the barcode is proportionally decreased. Furthermore, if the uppermost row or left most columns of the barcode are damaged, clock information will be lost making it difficult, if not impossible, to read out the data encoded in each data row as with other prior art systems.
U.S. Pat. No. 4,924,078 to Sant""Anselmo et al. describes a two-dimensional barcode system in which an orientation and/or timing cell border is included within the body of the barcode itself. For all cases in which the exact location, symbol size and data density are not known in advance of reading the barcode, the border is required by the Sant""Anselmo ""078 Patent and must be smooth and on at least two sides of the data area. In addition, timing cells are required when certain information is not a priori known, such as the number of cells per side. Here again, because the orientation and/or timing cell border is included within the barcode itself, the overall data capacity of the barcode is proportionally decreased. Furthermore, because critical information about decoding the barcode is extracted from the orientation border, damage to a single row or column of the embodiment of the Sant""Anselmo ""078 Patent in which the border is present on only two sides also makes it difficult, if not impossible to read out the data encoded within the barcode.
In co-pending patent application xe2x80x9cA Clock-Free Two-Dimensional Barcode and Method for Printing and Reading the Samexe2x80x9d, (Ser. No. 08/569,280, filed Dec. 8, 1995), now U.S. Pat. No. 5,862,270 (xe2x80x9cthe ""280 Applicationxe2x80x9d), the contents of which are explicitly incorporated by reference herein, a clock-less two-dimensional barcode with a border on at least one of the four sides of the barcode is described, which border is placed outside the confines of the barcode itself. The two-dimensional barcodes are called xe2x80x9cPanaMarksxe2x80x9d(copyright). As depicted in FIG. 1A, PanaMark 10 is printed in the low right hand corner of printed page 11, although this position is completely arbitrary. In the embodiment depicted in FIG. 1A, the remaining portion of printed page 11 is occupied by printed text 12. However, as one skilled in the art will appreciate, any type of computer-generated printed material, for example a spreadsheet or graphics, can be substituted for the printed text 12. The PanaMark 10 depicted in FIG. 1B includes a border 13 that is present on all four of its sides. Although, as is fully described in the ""280 Application, the border 13 is only needed on one of the four sides of the PanaMark 10, for aesthetic reasons it is typically included on all four sides.
It is therefore an object of the present invention to provide a clock free two-dimensional barcode representing digitally encoded data.
It is an additional object of the present invention to provide a border-less clock free two-dimensional barcode representing digitally encoded data.
Another object of the invention is to provide a border-less clock free two-dimensional barcode printed on a printed medium that is sufficiently robust to withstand damage to the medium.
A further object of the invention is to provide a border-less clock free two-dimensional barcode representing digitally encoded data, without the need for any internal blocks used for alignment purposes.
It is yet another object of this invention to encode information formatted in a border-less clock free two-dimensional barcode for printing on a printed medium.
An additional object of this invention is to provide a method of decoding information digitally encoded in the form of a border-less clock free two-dimensional barcode printed on a printed medium.
Various other objects, advantages and features of the present invention will become readily apparent from the ensuing detailed description and the novel features will be particularly pointed out in the appended claims.
These and other objectives are realized by a two-dimensional data barcode having encoded digital information in a bitmap formatted representation of randomized data bits having a selected pixel row and column length, with no border surrounding the barcode.
In one embodiment of this invention, a two-dimensional data barcode has encoded digital information in a bitmap formatted representation of randomized data bits having a selected pixel row and column length, with xe2x80x9cblackxe2x80x9d data pixels in each corner and no border surrounding the barcode. In another embodiment of this invention, there is no requirement that xe2x80x9cblackxe2x80x9d data pixels occupy each corner of the barcode.
As a further aspect of this invention, a method of encoding information, for printing on a printed medium, such as paper, is described. Information is first converted into a data stream having a sequence of binary characters representing data bits. The data stream is then randomized to produce approximately an equal number of xe2x80x9c0xe2x80x9d and xe2x80x9c1xe2x80x9d characters. Thereafter, the randomized data stream is formatted into a two-dimensional bitmap of rows and columns and printed onto the printed medium.
In another aspect of the invention, information is converted into a data stream having binary characters representing data bits. The data stream is mapped to produce digital data bits arranged in a two-dimensional bitmap of rows and columns having the four corner locations vacant. The four corner locations are set to the logical character representing a xe2x80x9cblackxe2x80x9d data pixel.
Another aspect of this invention relates to a method for mapping the data stream representing the information to be encoded to produce digital data bits arranged in a two-dimensional bitmap of rows and columns such that each data bit of a given block is separated from every other data bit within the same block by at least one row and one column, which ensures that the bitmap is robust with respect to row and column damage.
As a further aspect of this invention, a method for ensuring that the information encoded into the two-dimensional barcode is adequately randomized is presented. A number of alternative keys are available for randomization during the encoding process, so that if a first key does not produce an adequate level of randomization, a second key can be used. This process of testing additional keys continues until the randomization reaches a predefined level. During decoding, the error correcting code is used to select the most appropriate key for derandomization, as the improper key will produce excessive errors.
Preferably, in all embodiments of the two dimensional barcodes of this invention, the encoded information printed on the printed medium is randomized to safeguard against strings of contiguous pixels being the same color which may occur without randomization.
In another embodiment of this invention, information printed on a printed medium in the form of a two-dimensional bitmap of rows and columns of data pixels representing encoded data bits is decoded. The printed medium contains other information in addition to the bitmap. The printed medium on which the bitmap is printed is scanned, and the bitmap is located within the printed medium. The skew angle of the bitmap is determined with respect to the origin of the scanned printed medium, and if the angle is too large, the bitmap is deskewed. Once the bitmap is correctly aligned, it is cropped and the binary data from the data pixels is read to produce a two-dimensional digital array corresponding to the encoded data bits and corner bits, if present, respectively.
In a further embodiment of this aspect of this invention, a method of ensuring that the data is properly read from the deskewed, cropped bitmap is presented, whereby four alternative data streams are created by reading the data in four alternative directions, and the error correcting code is then used to select the data stream with the fewest errors for output.